package com.heima.leetcode.practice;

import java.util.*;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 49. 字母异位词分组
 * @date 2024/12/15 10:08
 */
public class E49 {
    /*
        ### 注意：
            - 这道题不能用字符串的hashCode作为key，因为那样的话每个字符串都是唯一的了
            - 这道题不能逐个计算字符的ASCII码之和，可能会有重复
            -
            - 可以选择字符串的排序结果作为key
            - 也可以选择长度26的数组作为key
     */

    /**
     * <h3>方法一：用排序结果作为key</h3>
     *
     * @param strArray 字符串数组
     * @return 分组后的结果
     */
    public List<List<String>> groupAnagrams1(String[] strArray) {
        // 1. 创建一个HashMap，用于存储排序后的字符串和对应的字符串列表
        HashMap<String, List<String>> map = new HashMap<>();
        // 2. 遍历字符串数组，对每个字符串进行排序，得到排序后的字符串作为key，将原字符串添加到对应的列表中
        for (String str : strArray) {
            char[] charArray = str.toCharArray();
            Arrays.sort(charArray);
            String key = new String(charArray);
            List<String> list = map.computeIfAbsent(key, k -> new ArrayList<>());
            list.add(str);
        }
        // 3. 将map的值转换为List并返回
        return new ArrayList<>(map.values());
    }

    /**
     * 自定义类，用于存储字符串的ASCII码数组
     */
    static class ArrayKey {
        private final int[] count;

        /**
         * 构造函数初始化数组
         *
         * @param s 字符串
         */
        public ArrayKey(String s) {
            this.count = new int[26];
            char[] charArray = s.toCharArray();
            for (char c : charArray) {
                count[c - 'a']++;
            }
        }

        /**
         * 重写equals方法
         *
         * @param o 对象
         * @return 是否相等
         */
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            ArrayKey arrayKey = (ArrayKey) o;
            return Arrays.equals(count, arrayKey.count);
        }

        /**
         * 重写hashCode方法
         *
         * @return hashCode
         */
        @Override
        public int hashCode() {
            return Arrays.hashCode(count);
        }
    }

    /**
     * <h3>方法二：用数组作为key</h3>
     *
     * @param strArray 字符串数组
     * @return 分组后的结果
     */
    public List<List<String>> groupAnagrams2(String[] strArray) {
        // 1. 创建一个HashMap，用于存储数组和对应的字符串列表
        HashMap<ArrayKey, List<String>> map = new HashMap<>();
        // 2. 遍历数组，将每个字符串转换为ArrayKey，并将其添加到对应的列表中
        for (String str : strArray) {
            ArrayKey key = new ArrayKey(str);
            List<String> list = map.computeIfAbsent(key, k -> new ArrayList<>());
            list.add(str);
        }
        // 3. 将map的值转换为List并返回
        return new ArrayList<>(map.values());
    }

    /**
     * <h3>方法三：使用AbstractList匿名内部类</h3>
     *
     * @param strArray 字符串数组
     * @return 分组后的结果
     */
    public List<List<String>> groupAnagrams3(String[] strArray) {
        return new AbstractList<List<String>>() {
            // 定义成员变量来存储异位词分组的结果。
            private final List<List<String>> list = new ArrayList<>();
            // 标记是否已经初始化
            private boolean initialized;

            /**
             * 初始化异位词词分组。
             * 该方法确保分组操作仅执行一次。
             */
            public void init() {
                // 如果list不为空，则表示分组已经初始化过，直接返回。
                if (initialized) return;
                // 使用HashMap存储具有相同排序值的字符串作为键，原始字符串作为值。
                HashMap<String, List<String>> map = new HashMap<>();
                for (String str : strArray) {
                    // 将字符串转换为字符数组，并进行排序。
                    char[] charArray = str.toCharArray();
                    Arrays.sort(charArray);
                    // 创建排序后的字符串作为键。
                    String key = new String(charArray);
                    // 获取当前排序字符串对应的列表，如果不存在则创建新列表。
                    List<String> group = map.computeIfAbsent(key, k -> new ArrayList<>());
                    // 将原始字符串添加到列表中。
                    group.add(str);
                }
                // 将所有分组的变位词列表添加到成员变量list中。
                list.addAll(map.values());
                initialized = true;
            }

            /**
             * 覆盖 AbstractList 的 get 方法，用于获取指定索引处的子列表。
             *
             * @param index 要获取的子列表的索引。
             * @return 返回指定索引处的子列表。
             */
            @Override
            public List<String> get(int index) {
                // 调用 init 方法以确保分组已完成。
                init();
                // 返回指定索引处的子列表。
                return list.get(index);
            }

            /**
             * 覆盖 AbstractList 的 size 方法，用于获取子列表的总数。
             *
             * @return 返回子列表的总数。
             */
            @Override
            public int size() {
                // 调用 init 方法以确保分组已完成。
                init();
                // 返回子列表的总数。
                return list.size();
            }
        };
    }

    /**
     * <h3>方法四：使用Java8的forEach和compute方法，自己写的</h3>
     *
     * @param strs 字符串数组
     * @return 分组后的结果
     */
    public List<List<String>> groupAnagrams4(String[] strs) {
        List<List<String>> result = new ArrayList<>();
        HashMap<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] charArray = str.toCharArray();
            Arrays.sort(charArray);
            String key = new String(charArray);
            map.compute(key, (k, v) -> {
                if (v == null) {
                    v = new ArrayList<>();
                }
                v.add(str);
                return v;
            });
        }
        map.forEach((k, v) -> result.add(v));
        return result;
    }
}
